home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 7675 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  3.2 KB
  1. Path: anvil.ugrad.cs.ubc.ca!not-for-mail
  2. From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Parsing an input stream?
  5. Date: 26 Feb 1996 09:24:51 -0800
  6. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  7. Message-ID: <4gsqd3INNl2@anvil.ugrad.cs.ubc.ca>
  8. References: <4gsep9$ho8@srvr1.engin.umich.edu>
  9. NNTP-Posting-Host: anvil.ugrad.cs.ubc.ca
  10.  
  11. In article <4gsep9$ho8@srvr1.engin.umich.edu>,
  12. byron lee newberry <newberry@news-server.engin.umich.edu> wrote:
  13.  >Hello,
  14.  >
  15.  >I am currently working on coding a symbolic manipulation program to perform
  16.  >tasks such as mutliplying out large polynomials, etc.  I have a pretty
  17.  >good idea how to program the beast except for the parsing of the input
  18.  >stream.  I have built up a very simple parser using basic string manipulation
  19.  >functions, but it is very crued.  Are libraries around that make this 
  20.  >a simplier job?  It would seem to me that parsing would be a common task.
  21.  >I appreciate any and all advice.  Thanks for your time.
  22.  
  23. I'd take the other poster's advice. Even if you are not working on UNIX, having
  24. your parser code prepared by lex and yacc is so much easier than hand-coding
  25. everything, and far more _maintainable_. It's easier to modify an abstract
  26. grammar specification with embedded C actions than a higgledy-piggledy mass of
  27. code.
  28.  
  29. The tools are also efficient. For example, code generated by lex is must faster
  30. than naively written C. GNU Flex, in particular, has a number of options for
  31. space/time tradeoffs enabling you to generate small lexical analyzers that are
  32. slow, or faster ones that use larger tables.
  33.  
  34. An example of a naively written lexical analyzer would be code which extracts a
  35. word from the input stream, and then compares it to a list of identifiers in
  36. sequence using strcmp(). Lex, on the other hand, can generate a single state
  37. machine that will accept any of those words simultaneously, and enter an
  38. acceptance state that can execute your C snippet.
  39.  
  40. A robust lex specification will result in a lexical analyzer function that can
  41. easily deal with comments, whitespace, identifiers, constants: in short, any
  42. kinds of tokens that you can dream of that can be matched by a regular
  43. expression.
  44.  
  45. Where lex stops, yacc takes off: you give it a grammar interspersed with C
  46. snippets, and it generates a parser that works in conjunction with lex (or
  47. possibly a hand-coded lexical analyzer function). You control the parser by
  48. carefully controlling the way you write the grammar. A typical use for yacc
  49. generated parsers is to construct an n-ary syntax tree which can be subject to
  50. further analysis elsewhere (type checking, translation, evaluation, etc).
  51.  
  52. A yacc-generated parser will automatically detect syntax errors and call an
  53. error handling function. As you become a Master Yaccster, you will learn to
  54. implement error productions, which are ``dummy'' elements added to the grammar
  55. to catch common user mistakes and attempt to do recovery and continue parsing.
  56. You can have your parser do things like say ``warning: you missed a closing
  57. brace in line 3''.
  58.  
  59. If you use lex and yacc, you can write a parser for a moderately complex
  60. programming language in one afternoon---even one that includes some rudimentary
  61. tree-building actions.
  62. -- 
  63.  
  64.